/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-01-16 11:03:45
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-09 23:26:55
 * @FilePath: \leetcode\4.寻找两个正序数组的中位数.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=4 lang=cpp
 *
 * [4] 寻找两个正序数组的中位数
 *
 * 方法：分治求解 topK 元素
 * - 中位数：第 (m+n+1)/2 个元素
 * - 寻找下标 i, j 使得 nums1[i-1] < nums2[j] && nums2[j-1] < nums1[i]
 *   nums1[0] nums1[1] ... nums1[i-1] <-> nums1[i] ... nums1[n-1]
 *   nums2[0] nums2[1] ... nums2[j-1] <-> nums2[j] ... nums2[m-1]
 * - 则 i, j 左边元素值全部小于右边元素值 故第 k=i+j 个元素值为 max{nums1[i-1], nums2[j-1]}
 * - 利用二分查找在对数时间确定下标 i, j
 * - 注意：mid_right 在奇数列中偏大
 */

#include <vector>
#include <iostream>

// @lc code=start
class Solution
{
public:
    double findMedianSortedArrays(std::vector<int> &nums1, std::vector<int> &nums2)
    {
        int len1 = nums1.size();
        int len2 = nums2.size();
        if (len1 > len2) // 保证二分搜索较短的 nums1
            return findMedianSortedArrays(nums2, nums1);

        if (len1 == 0) // 直接计算
            return static_cast<double>(nums2[(len2 - 1) / 2] + nums2[len2 / 2]) / 2.0;

        int k = (len1 + len2 + 1) / 2; // 中位数的位置
        int i = 0, j = 0;              // nums1 nums2 索引下标
        /* 二分搜索 i */
        int low1 = 0, high1 = len1;
        while (low1 <= high1)
        {
            i = (low1 + high1) / 2;
            j = k - i; // k = i+j
            /* nums1[i-1] < nums2[j] && nums2[j-1] < nums1[i] */
            if (i > 0 && j < len2 && nums1[i - 1] > nums2[j]) // nums1[i-1] 过大
                high1 = i - 1;
            else if (j > 0 && i < len1 && nums2[j - 1] > nums1[i]) // nums1[i] 过小
                low1 = i + 1;
            else
                break;
        }

        int mid_left = 0; // 中位数较小者
        if (i == 0)       // nums1[0] > nums2[len2-1]
            mid_left = nums2[j - 1];
        else if (j == 0) // nums2[0] > nums1[len1-1]
            mid_left = nums1[i - 1];
        else
            mid_left = std::max(nums1[i - 1], nums2[j - 1]);

        int mid_right = 0; // 中位数较大者 在奇数列中偏大
        if (i == len1)     // nums1[len1-1] < nums2[0]   i-1 = len1-1
            mid_right = nums2[j];
        else if (j == len2) // nums2[len2-1] < nums1[0]  j-1 = len2-1
            mid_right = nums1[i];
        else
            mid_right = std::min(nums1[i], nums2[j]);

        if ((len1 + len2) % 2 == 1)
            return mid_left;
        else
            return static_cast<double>(mid_left + mid_right) / 2.0;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;

    std::vector<int> nums1 = {2, 5, 7};
    std::vector<int> nums2 = {1, 3};

    std::cout << solution.findMedianSortedArrays(nums1, nums2) << std::endl;

    return 0;
}